home *** CD-ROM | disk | FTP | other *** search
/ Mac Power 1997 December / MACPOWER-1997-12.ISO.7z / MACPOWER-1997-12.ISO / AMUG / PROGRAMMING / Raven 1.2.sit / Raven 1.2 / • Extras • / SGI STL / vector.h < prev    next >
C/C++ Source or Header  |  1997-06-22  |  27KB  |  767 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  *
  15.  * Copyright (c) 1996
  16.  * Silicon Graphics Computer Systems, Inc.
  17.  *
  18.  * Permission to use, copy, modify, distribute and sell this software
  19.  * and its documentation for any purpose is hereby granted without fee,
  20.  * provided that the above copyright notice appear in all copies and
  21.  * that both that copyright notice and this permission notice appear
  22.  * in supporting documentation.  Silicon Graphics makes no
  23.  * representations about the suitability of this software for any
  24.  * purpose.  It is provided "as is" without express or implied warranty.
  25.  *
  26.  * Exception Handling:
  27.  * Copyright (c) 1997
  28.  * Mark of the Unicorn, Inc.
  29.  *
  30.  * Permission to use, copy, modify, distribute and sell this software
  31.  * and its documentation for any purpose is hereby granted without fee,
  32.  * provided that the above copyright notice appear in all copies and
  33.  * that both that copyright notice and this permission notice appear
  34.  * in supporting documentation.  Mark of the Unicorn makes no
  35.  * representations about the suitability of this software for any
  36.  * purpose.  It is provided "as is" without express or implied warranty.
  37.  *
  38.  * Adaptation:
  39.  * Copyright (c) 1997
  40.  * Moscow Center for SPARC Technology
  41.  *
  42.  * Permission to use, copy, modify, distribute and sell this software
  43.  * and its documentation for any purpose is hereby granted without fee,
  44.  * provided that the above copyright notice appear in all copies and
  45.  * that both that copyright notice and this permission notice appear
  46.  * in supporting documentation.  Moscow Center for SPARC Technology makes no
  47.  * representations about the suitability of this software for any
  48.  * purpose.  It is provided "as is" without express or implied warranty.
  49.  *
  50.  */
  51.  
  52. #ifndef __SGI_STL_VECTOR_H
  53. #define __SGI_STL_VECTOR_H
  54.  
  55. #include <stddef.h>
  56. # ifndef __SGI_STL_ALGOBASE_H
  57. #  include <algobase.h>
  58. # endif
  59. # ifndef __SGI_STL_ALLOC_H
  60. #  include <alloc.h>
  61. # endif
  62.  
  63. __BEGIN_STL_NAMESPACE
  64.  
  65. // ===================================================================================
  66. //    class __vector_base
  67. // ===================================================================================
  68. template <class T, class Alloc>
  69. class __vector_base  
  70. # if defined (__STL_DEBUG)
  71.     : public __safe_base
  72. # endif
  73. {
  74.     typedef __vector_base<T,Alloc> self;
  75. public:    
  76.     typedef T value_type;
  77.     typedef size_t size_type;
  78.     typedef T* pointer;
  79.     typedef const T* const_pointer;
  80. protected:
  81.     typedef simple_alloc<value_type, Alloc> data_allocator;
  82.     pointer start;
  83.     pointer finish;
  84.     pointer end_of_storage;
  85.  
  86.     void deallocate() {
  87.         if (start) {
  88.             __stl_debug_do(invalidate_all());
  89.             data_allocator::deallocate(start, (unsigned long) (end_of_storage - start));
  90.         }
  91.     }
  92. public:
  93.     __vector_base() : start(0), finish(0), end_of_storage(0) {
  94.         __stl_debug_do(safe_init(this));
  95.     }
  96.     
  97.     __vector_base(size_type n)
  98.     {
  99.         __stl_debug_do(safe_init(this));
  100.  
  101.         start = data_allocator::allocate(n);
  102.         finish = start;
  103.         end_of_storage = start + n;
  104.     }
  105.  
  106.     ~__vector_base() { 
  107.         destroy(start, finish);
  108.         deallocate();
  109.         __stl_debug_do(invalidate());
  110.     }
  111. # if defined (__STL_DEBUG)
  112. public:
  113.     bool dereferenceable(const value_type* it) const {
  114.         return (it>=start && it < finish);
  115.     }
  116.     bool valid_advance(const value_type* iter, ptrdiff_t n) const {
  117.         const value_type* advanced=iter+n;
  118.         return advanced>=start && advanced <=finish;
  119.     }
  120. # endif
  121. };
  122.  
  123. # if defined ( __STL_NESTED_TYPE_PARAM_BUG )
  124. #  define __pointer__             T*
  125. #  define __const_pointer__       const T*
  126. #  define __size_type__           size_t
  127. #  define __difference_type__     ptrdiff_t
  128. # else
  129. #  define __pointer__         pointer
  130. #  define __const_pointer__   const_pointer
  131. #  define __size_type__       size_type
  132. #  define __difference_type__ difference_type
  133. # endif
  134.  
  135. # if defined ( __STL_USE_ABBREVS )
  136. #  define  __vector_iterator       _V__It
  137. #  define  __vector_const_iterator _V__cIt
  138. # endif
  139.  
  140. # if defined (__STL_DEBUG)
  141. template <class T, class Alloc>
  142. struct __vector_const_iterator;
  143.  
  144. // ===================================================================================
  145. //    struct __vector_iterator
  146. // ===================================================================================
  147. template <class T, class Alloc>
  148. struct __vector_iterator : public __safe_base {
  149. private:
  150.     typedef __vector_iterator<T,Alloc> self;
  151.     typedef __safe_base super;
  152.     typedef __vector_base<T,Alloc> container;
  153. public:
  154.     typedef T value_type;
  155.     typedef value_type* iterator;
  156.     typedef value_type& reference;
  157.     typedef ptrdiff_t difference_type;
  158.     iterator iterator_;
  159. public:
  160.     __vector_iterator() : super(0)  {}
  161.     __vector_iterator(const super* c, const iterator& it) :
  162.         super(c), iterator_(it) {}
  163.     const container* owner() const { return (const container*)owner_; }
  164.     iterator  get_iterator() const { return iterator_; }
  165.  
  166.     reference operator*() const {
  167.         __stl_debug_check(__check_dereferenceable(*this));
  168.         return *iterator_;
  169.     }
  170.     self& operator++() {
  171.         __stl_debug_check(__check_advance(*this,1));
  172.         ++iterator_;
  173.         return *this;
  174.     }
  175.     self operator++(int) {
  176.         self tmp = *this;
  177.         ++iterator_;
  178.         return tmp;
  179.     }
  180.     self& operator--() {
  181.         __stl_debug_check(__check_advance(*this,-1));
  182.         --iterator_;
  183.         return *this;
  184.     }
  185.     self operator--(int) {
  186.         self tmp = *this;
  187.         --iterator_;
  188.         return tmp;
  189.     }
  190.     bool operator<(const self& y)  const {
  191.         __stl_debug_check(__check_same_owner(*this,y));
  192.         return (get_iterator() < y.get_iterator());
  193.     }
  194.     difference_type operator-(const self& x) const {
  195.         __stl_debug_check(__check_same_owner(*this,x));
  196.         return get_iterator()-x.get_iterator();
  197.     }
  198.     self& operator+=(difference_type n) {
  199.         __stl_debug_check(__check_advance(*this,n));
  200.         iterator_+=n;
  201.         return *this;
  202.     }
  203.     self& operator-=(difference_type n) { return *this += -n; }
  204.     self operator+(difference_type n) const {
  205.         self tmp = *this;
  206.         return tmp += n;
  207.     }
  208.     self operator-(difference_type n) const {
  209.         self tmp = *this;
  210.         return tmp -= n;
  211.     }
  212.     reference operator[](difference_type n) const { return *(*this + n); }
  213.  
  214.     bool operator==(const self& y) const {
  215.         __stl_debug_check(__check_same_owner(*this,y));
  216.         return get_iterator() == y.get_iterator();
  217.     }
  218.     bool operator!=(const self& y) const {
  219.         __stl_debug_check(__check_same_owner(*this,y));
  220.         return get_iterator() != y.get_iterator();
  221.     }
  222. };
  223.  
  224. // ===================================================================================
  225. //    struct __vector_const_iterator
  226. // ===================================================================================
  227. template <class T, class Alloc>
  228. struct __vector_const_iterator : public __safe_base {
  229. private:
  230.     typedef __vector_const_iterator<T,Alloc> self;
  231.     typedef __safe_base super;
  232.     typedef __vector_base<T,Alloc> container;
  233. public:
  234.     typedef T value_type;
  235.     typedef const value_type* const_iterator;
  236.     typedef const value_type& const_reference;
  237.     typedef ptrdiff_t difference_type;
  238.     const_iterator iterator_;
  239. public:                                     
  240.     __vector_const_iterator() : super(0) {}
  241.     __vector_const_iterator(const super* c, const_iterator it) :
  242.         super(c), iterator_(it) {}
  243.     __vector_const_iterator(const __vector_iterator<T,Alloc>& it) :
  244.         super(it), iterator_(it.get_iterator()) {}
  245.     const container* owner() const { return (const container*)owner_; }
  246.     const_iterator  get_iterator() const { return iterator_; }
  247.  
  248.     const_reference operator*() const {
  249.         __stl_debug_check(__check_dereferenceable(*this));
  250.         return *iterator_;
  251.     }
  252.     self& operator++() {
  253.         __stl_debug_check(__check_advance(*this,1));
  254.         ++iterator_;
  255.         return *this;
  256.     }
  257.     self operator++(int) {
  258.         self tmp = *this;
  259.         ++iterator_;
  260.         return tmp;
  261.     }
  262.     self& operator--() {
  263.         __stl_debug_check(__check_advance(*this,-1));
  264.         --iterator_;
  265.         return *this;
  266.     }
  267.     self operator--(int) {
  268.         self tmp = *this;
  269.         --iterator_;
  270.         return tmp;
  271.     }
  272.     bool operator<(const self& y)  const {
  273.         __stl_debug_check(__check_same_owner(*this,y));
  274.         return (get_iterator() < y.get_iterator());
  275.     }
  276.     difference_type operator-(const self& x) const {
  277.         __stl_debug_check(__check_same_owner(*this,x));
  278.         return get_iterator()-x.get_iterator();
  279.     }
  280.     self& operator+=(difference_type n) {
  281.         __stl_debug_check(__check_advance(*this,n));
  282.         iterator_+=n;
  283.         return *this;
  284.     }
  285.     self& operator-=(difference_type n) { return *this += -n; }
  286.     self operator+(difference_type n) const {
  287.         self tmp = *this;
  288.         return tmp += n;
  289.     }
  290.     self operator-(difference_type n) const {
  291.         self tmp = *this;
  292.         return tmp -= n;
  293.     }
  294.     const_reference operator[](difference_type n) const { return *(*this + n); }
  295.  
  296.     bool operator==(const self& y) const {
  297.         __stl_debug_check(__check_same_owner(*this,y));
  298.         return get_iterator() == y.get_iterator();
  299.     } 
  300.     bool operator!=(const self& y) const {
  301.         __stl_debug_check(__check_same_owner(*this,y));
  302.         return get_iterator() != y.get_iterator();
  303.     }
  304. };
  305.  
  306. # define __iterator__       __vector_iterator<T,Alloc>
  307. # define __const_iterator__ __vector_const_iterator<T,Alloc>
  308. template <class T, class Alloc>
  309. inline T* value_type(const  __iterator__&) { return (T*) 0; }
  310. template <class T, class Alloc>
  311. inline ptrdiff_t* distance_type(const  __iterator__&) { return (ptrdiff_t*) 0; }
  312. template <class T, class Alloc>
  313. inline random_access_iterator_tag
  314. iterator_category(const __iterator__&) { return random_access_iterator_tag();}
  315. template <class T, class Alloc>
  316. inline T* value_type(const  __const_iterator__&) { return (T*) 0; }
  317. template <class T, class Alloc>
  318. inline ptrdiff_t* distance_type(const  __const_iterator__&) { return (ptrdiff_t*) 0; }
  319. template <class T, class Alloc>
  320. inline random_access_iterator_tag
  321. iterator_category(const __const_iterator__&) { return random_access_iterator_tag();}
  322. # else
  323. #  define __iterator__       __pointer__
  324. #  define __const_iterator__ __const_pointer__  
  325. # endif
  326.  
  327. __BEGIN_STL_FULL_NAMESPACE
  328. #  define vector __WORKAROUND_RENAME(vector)
  329.  
  330. // ===================================================================================
  331. //    class vector
  332. // ===================================================================================
  333. template <class T, __DFL_TYPE_PARAM(Alloc,alloc)>
  334. class vector : protected __vector_base<T, Alloc> {
  335.     typedef __vector_base<T,Alloc> super;
  336.     typedef vector<T,Alloc> self;
  337. public:
  338.     typedef T value_type;
  339.     typedef value_type* pointer;
  340.     typedef const value_type* const_pointer;
  341.     typedef value_type& reference;
  342.     typedef const value_type& const_reference;
  343.     typedef ptrdiff_t difference_type;
  344.     typedef size_t size_type;
  345.     typedef __iterator__ iterator;
  346.     typedef __const_iterator__ const_iterator;
  347.     typedef reverse_iterator<const_iterator, value_type, const_reference, 
  348.             difference_type>  const_reverse_iterator;
  349.     typedef reverse_iterator<iterator, value_type, reference, difference_type>
  350.     reverse_iterator;
  351. protected:
  352.     void insert_aux(pointer position, const T& x);
  353. public:
  354.     pointer begin_() { return start; }
  355.     const_pointer begin_() const { return start; }
  356.     pointer end_() { return finish; }
  357.     const_pointer end_() const { return finish; }
  358. # if defined (__STL_DEBUG)
  359. #   define __ptr(x) x.get_iterator()  
  360.     iterator begin() { return iterator(this,start); }
  361.     const_iterator begin() const { return const_iterator(this,start); }
  362.     iterator end() { return iterator(this,finish); }
  363.     const_iterator end() const { return const_iterator(this,finish); }
  364.     void invalidate(const pointer& first, const pointer& last) {
  365.         __invalidate_range(this, first, last, iterator());
  366.     }
  367. # else
  368. #   define __ptr(x) x    
  369.     iterator begin() { return start; }
  370.     const_iterator begin() const { return start; }
  371.     iterator end() { return finish; }
  372.     const_iterator end() const { return finish; }
  373. # endif
  374.     reverse_iterator rbegin() { return reverse_iterator(end()); }
  375.     const_reverse_iterator rbegin() const { 
  376.         return const_reverse_iterator(end()); 
  377.     }
  378.     reverse_iterator rend() { return reverse_iterator(begin()); }
  379.     const_reverse_iterator rend() const { 
  380.         return const_reverse_iterator(begin()); 
  381.     }
  382.     size_type size() const { return size_type(end_() - begin_()); }
  383.     size_type max_size() const { return size_type(-1)/sizeof(T); }
  384.     size_type capacity() const { return size_type(end_of_storage - start); }
  385.     bool empty() const { return begin_() == end_(); }
  386.     reference operator[](size_type n) { 
  387.         __stl_verbose_assert(n<size(), __STL_MSG_OUT_OF_BOUNDS);
  388.         return *(start+n); 
  389.     }
  390.     const_reference operator[](size_type n) const { 
  391.         __stl_verbose_assert(n<size(), __STL_MSG_OUT_OF_BOUNDS);
  392.         return *(start+n); 
  393.     }
  394.     reference at(size_type n) {             // ･･･ﾊJDJ (note that CD2 sez this throws if index is bad)
  395.         if (n >= size())
  396.             throw out_of_range("vector::at() range exception");
  397.         return *(start+n); 
  398.     }
  399.     const_reference at(size_type n) const {  // ･･･ﾊJDJ (this is in CD2)
  400.         if (n >= size())
  401.             throw out_of_range("vector::at() range exception");
  402.         return *(start+n); 
  403.     }
  404.    vector() {}
  405.     vector(size_type n, const T& value) : super(n) {
  406.         finish = uninitialized_fill_n(start, n, value);
  407.     }
  408.     explicit vector(size_type n) : super(n) {
  409.         finish = __default_initialize_n(start, n);
  410.     }
  411.     vector(const self& x) : super((unsigned long) (x.end_() - x.begin_())) {
  412.         finish = uninitialized_copy(x.begin_(), x.end_(), start);
  413.     }
  414.     vector(const_iterator first, const_iterator last) {
  415.         __stl_debug_check(__check_range(first,last));
  416.         size_type n = 0;
  417.         distance(__ptr(first), __ptr(last), n);
  418.         start = finish = data_allocator::allocate(n);
  419.         end_of_storage = start+n;
  420.         finish = uninitialized_copy(__ptr(first), __ptr(last), start);        
  421.     }
  422. # if defined ( __STL_DEBUG )
  423.     vector(const_pointer first, const_pointer last) {
  424.         __stl_debug_check(__check_range(first,last));
  425.         size_type n = (unsigned long) (last-first);
  426.         start = finish = data_allocator::allocate(n);
  427.         end_of_storage = start+n;
  428.         finish = uninitialized_copy(first, last, start);
  429.     }
  430. # endif
  431.     ~vector() {}
  432.     self& operator=(const self& x);
  433.     void reserve(size_type n) {
  434.         const size_type old_size(size());
  435.         if (capacity() < n) {
  436.             pointer tmp = data_allocator::allocate(n);
  437.             __TRY {
  438.                 uninitialized_copy(begin_(), end_(), tmp);
  439.                 destroy(start, finish);
  440.                 deallocate();
  441.                 finish = tmp + old_size;
  442.                 start = tmp;
  443.                 end_of_storage = begin_() + n;
  444.             }
  445. #  if defined (__STL_USE_EXCEPTIONS)
  446.             catch(...) {
  447.                 data_allocator::deallocate(tmp, n);
  448.                 throw;
  449.             }
  450. #  endif
  451.         }
  452.     }
  453.     reference front() { 
  454.         __stl_verbose_assert(!empty(), __STL_MSG_EMPTY_CONTAINER);
  455.         return *begin_(); 
  456.     }
  457.     const_reference front() const { 
  458.         __stl_verbose_assert(!empty(), __STL_MSG_EMPTY_CONTAINER);
  459.         return *begin_(); 
  460.     }
  461.     reference back() { 
  462.         __stl_verbose_assert(!empty(), __STL_MSG_EMPTY_CONTAINER);
  463.         return *(end_() - 1); 
  464.     }
  465.     const_reference back() const { 
  466.         __stl_verbose_assert(!empty(), __STL_MSG_EMPTY_CONTAINER);
  467.         return *(end_() - 1); 
  468.     }
  469.     void push_back(const T& x) {
  470.         if (finish != end_of_storage) {
  471.             construct(finish, x);
  472.             ++finish;
  473.         } else
  474.             insert_aux(end_(), x);
  475.     }
  476.     void swap(self& x) {
  477.         __stl_debug_do(swap_owners(x));
  478.         __STL_NAMESPACE::swap(start, x.start);
  479.         __STL_NAMESPACE::swap(finish, x.finish);
  480.         __STL_NAMESPACE::swap(end_of_storage, x.end_of_storage);
  481.     }
  482.     iterator insert(iterator position, const T& x) {
  483.         __stl_debug_check(__check_if_owner(this,position));
  484.         size_type n = (unsigned long) (__ptr(position) - begin_());
  485.         if (finish != end_of_storage && __ptr(position) == end_()) {
  486.             construct(finish, x);
  487.             ++finish;
  488.         } else
  489.             insert_aux(__ptr(position), x);
  490.         return begin()+(long)n;
  491.     }
  492.     iterator insert(iterator position) { return insert(position, T()); }
  493.     void insert (iterator position, size_type n, const T& x);
  494.     void insert (iterator position, const_iterator first, const_iterator last) 
  495. # if defined ( __STL_DEBUG )
  496.     {    
  497.         __stl_debug_check(__check_same_owner(first,last));
  498.         insert(position, __ptr(first), __ptr(last));
  499.     }
  500.     void insert (iterator position, const_pointer first, 
  501.                  const_pointer last);
  502. # else
  503.     ;
  504. # endif
  505.  
  506.     void pop_back() {
  507.         __stl_verbose_assert(!empty(), __STL_MSG_EMPTY_CONTAINER);
  508.         --finish;
  509.         destroy(finish);
  510.     }
  511.     void erase(iterator position) {
  512.         __stl_debug_check(__check_if_owner(this,position));
  513.         __stl_verbose_assert(__ptr(position)!=finish,__STL_MSG_ERASE_PAST_THE_END);
  514.         if (__ptr(position) + 1 != end_())
  515.             copy(__ptr(position) + 1, end_(), __ptr(position));
  516.         __stl_debug_do(invalidate(__ptr(position),finish));
  517.         --finish;
  518.         destroy(finish);
  519.     }
  520.     void erase(iterator first, iterator last) {
  521.         __stl_debug_check(__check_if_owner(this,first)
  522.                           &&__check_range(first,last));
  523.         pointer i = copy(__ptr(last), end_(), __ptr(first));
  524.         destroy(i, finish);
  525.         __stl_debug_do(invalidate(__ptr(first),finish));
  526.         finish = finish - (__ptr(last) - __ptr(first)); 
  527.     }
  528.     void resize(size_type new_size, const T& x) {
  529.         if (new_size < size()) 
  530.             erase(begin() + (long) new_size, end());
  531.         else
  532.             insert(end(), new_size - size(), x);
  533.     }
  534.     void resize(size_type new_size) { resize(new_size, T()); }
  535.     void clear() { erase(begin(), end()); }
  536. };
  537.  
  538. template <class T, class Alloc>
  539. vector<T, Alloc>& vector<T, Alloc>::operator=(const vector<T, Alloc>& x) {
  540.     if (&x == this) return *this;
  541.     __stl_debug_do(invalidate_all());
  542.     if (x.size() > capacity()) {
  543.         destroy(start, finish);
  544.         deallocate();
  545.         start = finish = 0;
  546.         start = finish = data_allocator::allocate(x.size());
  547.         end_of_storage = start + (x.size());
  548.         uninitialized_copy(x.begin_(), x.end_(), start);
  549.     } else if (size() >= x.size()) {
  550.         pointer i = copy(x.begin_(), x.end_(), begin_());
  551.         destroy(i, finish);
  552.     } else {
  553.         copy(x.begin_(), x.begin_() + size(), begin_());
  554.         uninitialized_copy(x.begin_() + size(), x.end_(), begin_() + size());
  555.     }
  556.     finish = begin_() + x.size();
  557.     return *this;
  558. }
  559.  
  560. template <class T, class Alloc>
  561. void vector<T, Alloc>::insert_aux(__pointer__ position, const T& x) {
  562.     if (finish != end_of_storage) {
  563.         construct(finish, *(finish - 1));
  564.         ++finish;
  565.         T x_copy = x;
  566.         copy_backward(position, finish - 2, finish-1);
  567.         *position = x_copy;
  568.     } else {
  569.         const size_type old_size = size();
  570.         const size_type len = old_size != 0 ? 2 * old_size : 1;
  571.         pointer tmp = data_allocator::allocate(len);
  572.         pointer tmp_end = tmp;
  573.         __TRY {
  574.             tmp_end = uninitialized_copy(begin_(), position, tmp);
  575.             construct(tmp_end, x);
  576.             ++tmp_end;
  577.             tmp_end = uninitialized_copy(position, end_(), tmp_end);
  578.             destroy(begin_(), end_());
  579.             deallocate();
  580.             end_of_storage = tmp + len;
  581.             finish = tmp_end;
  582.             start = tmp;
  583.         }
  584. #  if defined (__STL_USE_EXCEPTIONS)
  585.         catch(...) {
  586.             destroy(tmp, tmp_end);
  587.             data_allocator::deallocate(tmp, len);
  588.             throw;
  589.         }
  590. #  endif
  591.     }
  592. }
  593.  
  594. template <class T, class Alloc>
  595. # if defined ( __STL_DEBUG )
  596. void vector<T, Alloc>::insert(__iterator__ pos, __size_type__ n, const T& x) {
  597.     __stl_debug_check(__check_if_owner(this,pos));
  598.     pointer position=__ptr(pos);
  599. # else
  600. void vector<T, Alloc>::insert(__iterator__ position, __size_type__ n, const T& x) {
  601. # endif
  602.     if (n == 0) return;
  603.     if (end_of_storage - finish >= (difference_type)n) {
  604.         pointer old_end = end_();
  605.         size_type distance_to_end = (unsigned long) (end_() - position);
  606.         if (distance_to_end > n) {
  607.             uninitialized_copy(end_() - n, end_(), end_());
  608.             finish += n;
  609.             copy_backward(position, old_end - n, old_end);
  610.             fill(position, position + n, x);
  611.         } else {
  612.             uninitialized_fill_n(end_(), n - distance_to_end, x);
  613.             finish += n - distance_to_end;
  614.             uninitialized_copy(position, old_end, end());
  615.             finish += distance_to_end;
  616.             fill(position, old_end, x);
  617.         }
  618.         __stl_debug_do(invalidate(position,old_end));
  619.     } else {
  620.         const size_type old_size = size();        
  621.         const size_type len = old_size + max(old_size, n);
  622.         pointer tmp = data_allocator::allocate(len);
  623.         pointer tmp_end = tmp;
  624.         __TRY {
  625.             tmp_end = uninitialized_copy(begin_(), position, tmp);
  626.             tmp_end = uninitialized_fill_n(tmp_end, n, x);
  627.             tmp_end = uninitialized_copy(position, end_(), tmp_end);
  628.             destroy(begin_(), end_());
  629.             deallocate();
  630.             end_of_storage = tmp + len;
  631.             finish = tmp_end;
  632.             start = tmp;
  633.         } 
  634. #  if defined (__STL_USE_EXCEPTIONS)
  635.         catch(...) {
  636.             destroy(tmp, tmp_end);
  637.             data_allocator::deallocate(tmp, len);
  638.             throw;
  639.         }
  640. #  endif
  641.     }
  642. }
  643.     
  644. template <class T, class Alloc>
  645. # if defined ( __STL_DEBUG )
  646. void vector<T, Alloc>::insert(__iterator__ pos, __const_pointer__ first,
  647.                               __const_pointer__ last) {
  648.     __stl_debug_check(__check_if_owner(this,pos)
  649.                       &&__check_range(first,last));
  650.     pointer position=__ptr(pos);
  651. # else
  652. void vector<T, Alloc>::insert(__iterator__ position, __const_iterator__ first,
  653.                               __const_iterator__ last) {
  654. # endif
  655.     if (first == last) return;
  656.     size_type n = 0;
  657.     distance(first, last, n);
  658.     if (end_of_storage - finish >= (difference_type)n) {
  659.         pointer old_end = end_();
  660.         size_type distance_to_end = end_() - position;
  661.         if (end_() - position > (difference_type)n) {
  662.             uninitialized_copy(end_() - n, end_(), end_());
  663.             finish += n;
  664.             copy_backward(position, old_end - n, old_end);
  665.             copy(first, last, position);
  666.         } else {
  667.             uninitialized_copy(first + distance_to_end, last, end_());
  668.             finish += n - distance_to_end;
  669.             uninitialized_copy(position, old_end, end_());
  670.             finish += distance_to_end;
  671.             copy(first, first + distance_to_end, position);
  672.         }
  673.         __stl_debug_do(invalidate(position,old_end));
  674.     } else {
  675.         const size_type old_size = size();
  676.         const size_type len = old_size + max(old_size, n);
  677.         pointer tmp = data_allocator::allocate(len);
  678.         pointer tmp_end = tmp;
  679.         __TRY {
  680.             tmp_end = uninitialized_copy(begin_(), position, tmp);
  681.             tmp_end = uninitialized_copy(first, last, tmp_end);
  682.             tmp_end = uninitialized_copy(position, end_(), tmp_end);
  683.             destroy(begin_(), end_());
  684.             deallocate();
  685.             end_of_storage = tmp + len;
  686.             finish = tmp_end;
  687.             start = tmp;
  688.         }
  689. #  if defined (__STL_USE_EXCEPTIONS)
  690.         catch(...) {
  691.             destroy(tmp, tmp_end);
  692.             data_allocator::deallocate(tmp, len);
  693.             throw;
  694.         }
  695. #  endif
  696.     }
  697. }
  698.  
  699. // do a cleanup
  700. # undef  vector
  701. # undef  __iterator__
  702. # undef  __const_iterator__
  703. # undef  __pointer__
  704. # undef  __const_pointer__
  705. # undef  __size_type__
  706. # undef  __ptr
  707. # undef  __difference_type__
  708.  
  709. // provide a uniform way to access full funclionality
  710. #  define __vector__ __FULL_NAME(vector)
  711.  
  712. __END_STL_FULL_NAMESPACE
  713.  
  714. # if ! defined (__STL_DEFAULT_TYPE_PARAM)
  715. // provide a "default" vector adaptor
  716. template <class T>
  717. class vector : public __vector__<T,alloc>
  718. {
  719.     typedef vector<T> self;
  720. public:
  721.     typedef __vector__<T,alloc> super;
  722.     __CONTAINER_SUPER_TYPEDEFS
  723.     __IMPORT_SUPER_COPY_ASSIGNMENT(vector)
  724.     vector() {}
  725.     explicit vector(size_type n, const T& value) : super(n, value) { }
  726.     explicit vector(size_type n) : super(n) { }
  727. # if defined ( __STL_DEBUG )
  728.     vector(const value_type* first, const value_type* last) : super(first,last) { }
  729. # endif
  730.     vector(const_iterator first, const_iterator last) : super(first,last) { }
  731.     ~vector() {}
  732. };
  733.  
  734. #  if defined (__STL_BASE_MATCH_BUG)
  735. template <class T>
  736.     inline bool operator==(const vector<T>& x, const vector<T>& y) {
  737.     typedef  __vector__<T,alloc> super;
  738.     return operator == ((const super&)x,(const super&)y);
  739. }
  740.  
  741. template <class T>
  742.     inline bool operator<(const vector<T>& x, const vector<T>& y) {
  743.     typedef  __vector__<T,alloc> super;
  744.     return operator < ((const super&)x,(const super&)y);
  745. }
  746. #  endif /* __STL_BASE_MATCH_BUG */
  747. # endif /* __STL_DEFAULT_TEMPLATE_PARAM */
  748.  
  749. template <class T, class Alloc>
  750.     inline bool operator==(const __vector__<T, Alloc>& x, const __vector__<T, Alloc>& y) {
  751.     return x.size() == y.size() && equal(x.begin_(), x.end_(), y.begin_());
  752. }
  753.  
  754. template <class T, class Alloc>
  755.     inline bool operator<(const __vector__<T, Alloc>& x, const __vector__<T, Alloc>& y) {
  756.     return lexicographical_compare(x.begin_(), x.end_(), y.begin_(), y.end_());
  757. }
  758.  
  759. # if defined (__STL_CLASS_PARTIAL_SPECIALIZATION )
  760. template <class T, class Alloc>
  761.     inline void swap(__vector__<T,Alloc>& a, __vector__<T,Alloc>& b) { a.swap(b); }
  762. # endif
  763. // close std namespace
  764. __END_STL_NAMESPACE
  765.  
  766. #endif
  767.